package Array;

/**
 * 45. 跳跃游戏 II
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 * 0 <= j <= nums[i]
 * i + j < n
 * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 * 解题思路：
 *   这道题与55题题意没有区别，但是此题需要计算最小跳跃次数，相当于基于55题的贪心算法进行修改
 *  要解决这道题，我们需要考虑贪心的思路， 用局部的最优解推导出全局最优解。
 *  我们可以想到，在每个位置，我们可以尽可能地往前跳，同时记录每一步能到达的最远距离。
 *  为了维护最小的跳跃次数， 则每次跳跃都得考虑最大， 所以我们需要维护能到达当前步骤的最远距离和下一步能到达的最远距离（当前步骤上的元素值）.
 * 解题步骤:
 *  1: 初始化两个变量 maxReach 和 steps 分别用来记录当前步骤能到达的最远距离和当前步骤的跳跃次数。
 *  maxReach 初始化为 nums[0]，因为从第一个元素开始跳跃，steps 初始化为1，因为至少需要一步从第一个元素开始。
 *  2: 遍历数组，对于每个位置 i，我们更新 maxReach 和 steps 的值。
 *  3: 使用一个变量nextMaxReach来记录当前步骤内，能够达到下一步的最远距离, Math.max(nextMaxReach,i+nums[i]) 下一步能够到达的最远距离
 *  4： 当我们到达当前步骤能跳到最远距离时（i > maxReach）, 我们需要使用 nextMaxReach 来更新 maxReach，并增加跳跃次数。
 *  5： 重复这个过程，直到我们达到或者超过数组的最后一个位置
 */
public class CanJumpII {
    public int jump(int[] nums) {
        if(nums.length <=1){
            return 0;
        }
        int step = 1; // 最小步数，至少需要1步
        int maxReach = nums[0]; // 当前位置上能够到达的最远距离
        int nextMaxReach = nums[0]; // 下一步能够到达的最远距离,默认也是 nums[0] 因为是从0开始跳起，0+nums[0]
        // 计算从1开始算起
        for (int i = 1; i < nums.length ; i++) {
            // 如果 i 已经超过了当前位置上能够到达的最远距离，那么就需要更新步数 和 下一步的最远距离
            if(i > maxReach){
                step ++;
                maxReach = nextMaxReach;
            }

            // 下一步能够到达的最远距离
            nextMaxReach = Math.max(nextMaxReach,i+nums[i]);
        }
        return step;
    }
}
